package LeetCode.字符串;

/**
 * @Project: data-structure-and-algorithms
 * @Package: LeetCode.字符串
 * @ClassName: t5
 * @Author: zhouyihe
 * @Date: 2025/11/4 10:38
 * @Description: 最长回文子串
 */
public class t5 {
    public static void main(String[] args) {
        String str = "babad";
        System.out.println(longestPalindrome(str));
        // System.out.println(longestPalindrome1(str));
        // System.out.println(longestPalindrome2(str));
    }

    // 暴力解题
    private static String longestPalindrome(String str) {
        int len = str.length();
        if (len < 2) {
            return str;
        }
        int maxLen = 1;
        int begin = 0;

        char[] chars = str.toCharArray();
        for (int i = 0; i < len - 1; i++) {
            for (int j = i + 1; j < len; j++){
                if (chars[i] == chars[j]){
                    if (j - i + 1 > maxLen && isPalindromic(chars,i,j)){
                        maxLen = j - i + 1;
                        begin = i;
                    }
                }
            }
        }
        return str.substring(begin,begin + maxLen);
    }

    /**
     * 判断字符数组中指定范围的子串是否为回文串
     * @param chars 字符数组
     * @param i 起始索引
     * @param j 结束索引
     * @return 如果指定范围内的字符序列是回文串则返回true，否则返回false
     */
    private static boolean isPalindromic(char[] chars, int i, int j) {
        // 使用双指针从两端向中间比较字符是否相等
        while (i < j){
            if (chars[i] != chars[j]){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }


    // 动态规划
    // private static String longestPalindrome1(String str) {
    //
    // }
    //
    // private static String longestPalindrome2(String str) {
    // }


}
